260

17

Genomics

The third mode is called a listing or derivation; it consists of an alternating series of

sequences and elementary operations, successive sequences differing only in accord

with the interspersed elementary operation, as illustrated below

upper I left parenthesis s Subscript a Baseline comma s Subscript b Baseline right parenthesis equals upper I left parenthesis s Subscript b Baseline comma s Subscript a Baseline right parenthesis equals upper I left parenthesis s Subscript a Baseline right parenthesis minus upper I left parenthesis s Subscript a Baseline vertical bar s Subscript b Baseline right parenthesis equals upper I left parenthesis s Subscript b Baseline right parenthesis minus upper I left parenthesis s Subscript b Baseline vertical bar s Subscript a Baseline right parenthesis period

INDUSTRY

delete D

INUSTRY

delete U

INSTRY

substitute Y by S

INSTRS

insert E

INSTERS

insert E

INSTERES

delete S

INTERES

insert T

INTEREST

Listing is of less practical use, but is a richer mode of analysis than the previous two.

17.4.4

Dynamic Programming Algorithms

The concept of dynamic programming comes from operations research, where it is

commonly used to solve problems that can be divided into stages with a decision

required at each stage. A good generic example is the problem of finding the shortest

path on a graph. The decisions are where to go next at each node. It is characteristic

that the decision at one stage transforms that state into a state in the next stage. Once

that is done, from the viewpoint of the current state the optimal decision for the

remaining states does not depend on the previous states or decisions. Hence, it is not

necessary to know how a node was reached, only that it was reached. A recursive

relationship identifies the optimal decision for stage upper MM, given that stage upper M plus 1M + 1 has

already been solved; the final stage must be solvable by itself.

The following is a generic dynamic programming algorithm (DPA) for comparing

two strings upper S Baseline 1S1 and upper S Baseline 2S2 with upper M left bracket i comma j right bracket equalsM[i, j] = cost or score of upper S Baseline 1 left bracket 1 period period i right bracketS1[1..i] and upper S Baseline 2 left bracket 1 period period j right bracketS2[1.. j]: ¹⁹

19 Allison et al. (1999).